/*
ID: quxiao82
LANG: C++
PROG: ditch
*/

#include <iostream>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <memory.h>
using namespace std;

const int MAX = 205;
const int INF = 2000000000;

struct Active 
{
	int v;
};

priority_queue<Active> pq;
int c[MAX][MAX];
int f[MAX][MAX];
int n, m;
int s, t;
int maxFlow;
int d[MAX];
int e[MAX];				
int visited[MAX];
int q[1000000];
int head, tail;


bool operator< (Active a1, Active a2)
{
	return ( d[a1.v] > d[a2.v] );
}


bool Input ()
{
	if ( scanf("%d%d", &m, &n) == EOF )
		return false;
	int i, a, b, l;
	s = 0;
	t = n-1;
	memset(c, 0, sizeof(c));
	memset(f, 0, sizeof(f));
	for (i=0; i<m; i++)
	{
		scanf("%d%d%d", &a, &b, &l);
		c[a-1][b-1] += l;
	}
	return true;
}


bool BFS ()
{
	int i, temp;
	head = tail = 0;
	memset(d, -1, sizeof(d));
	d[t] = 0;
	q[tail] = t;
	tail ++;

	while ( head != tail )
	{
		temp = q[head];
		head ++;
		for (i=0; i<n; i++)
		{
			if ( f[i][temp] < c[i][temp] && d[i] == -1 )
			{
				d[i] = d[temp] + 1;
				q[tail] = i;
				tail ++;
			}
		}
		if ( d[s] != -1 )
			return true;
	}
	return false;

}


void Check (int cur)
{
	int i, a;
	Active temp;
	for (i=0; i<n; i++)
	{
		if ( d[cur] == d[i] + 1 && e[cur] > 0 && f[cur][i] < c[cur][i] )
		{
			a = c[cur][i] - f[cur][i];
			if ( a > e[cur] )
				a = e[cur];
			f[cur][i] += a;
			f[i][cur] -= a;
			e[cur] -= a;
			e[i] += a;

			if ( e[i] == a && i != s && i != t )
			{
				temp.v = i;
				pq.push(temp);
			}
		}
	}

	if ( e[cur] > 0 && cur != s && cur != t )
	{
		d[cur] = INF;
		for (i=0; i<n; i++)
		{
			if ( f[cur][i] < c[cur][i] && d[cur] > d[i] + 1 )
				d[cur] = d[i] + 1;
		}
		temp.v = cur;
		pq.push(temp);
	}
}

void PreFlowPush ()
{
	int i;
	Active temp;
	while ( !pq.empty() )
		pq.pop();

	BFS ();
	d[s] = n;

	memset(e, 0, sizeof(e));

	for (i=0; i<n; i++)
	{
		if ( f[s][i] < c[s][i] )
		{
			e[i] = f[s][i] = c[s][i];
			f[i][s] = -f[s][i];
			if ( i != t && e[i] > 0 )
			{
				temp.v = i;
				pq.push(temp);
			}
		}
	}

	while ( !pq.empty() )
	{
		temp = pq.top();
		pq.pop();
		Check(temp.v);
	}

	maxFlow = 0;
	for (i=0; i<n; i++)
		maxFlow += f[s][i];

	printf("%d\n", maxFlow);
}

int main ()
{
	freopen( "ditch.in", "r" , stdin );
	freopen( "ditch.out", "w" , stdout );

	while ( Input() )
	{
		PreFlowPush();
	}

	return 0;
}